
#ifdef LIST_H
#define LIST_H


template <typename Object>

class List{
    private:
    struct Node
    {
        Object data;
        Node *prev;
        Node *next;
    };
    int theSize;
    Node *head;
    Node *tail;

    public:
    class iterator;
    class const_iterator;
    List(){
        init();
    }
    List(const List &rhs){
        init();
        for(auto &x:rhs)
            push_back(x);
    }
    ~List(){
        clear();
        delete head;
        delete tail;
    }
    List & operator=(const List & rhs){
        List copy =rhs;
        std::swap(*this, copy);
        return *this;
    }
    List & operator=(const List && rhs) :theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}{
        rhs.theSize = 0;
        rhs.head = nullptr;
        rhs.tail = nullptr;
    }
    void init(){
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;

    }
    iterator begin(){
        return {head->next};
    }
    const_iterator begin() const{
        return {head->next};
    }

    int size() const{
        return theSize;
    }
    bool empty() const{
        return (size() == 0);
    }
    void clear(){
        while(!empty())
            pop_front();
    }
    Object & front(){
        return *begin();
    }
    const Object & front() const{
        return *begin();
    }
    Object & back(){
        return *--end();
    }
    const Object & back() const{
        return *--end();
    }
    void push_front(const Object &x){
        insert(begin(),x);
    }
    void push_front(Object &&x){
        insert(begin(),std::move(x));
    }
    void push_back(const Object &x){
        insert(end(),x);
    }
    void push_back(Object &&x){
        insert(end(),std::move(x));
    }
    void pop_front(){
        erase(begin());
    }
    iterator insert(iterator itr, const Object &x){
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{x, p->prev,p}};
    }
    iterator insert(iterator itr, Object &&x){
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{std::move(x),p->prev,p}};
    }
    iterator erase(iterator itr){
        Node *p = itr.current;
        iterator retVal{p->next};
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;
        return retVal;
    }
    iterator erase(iterator from, iterator to){
        for(iterator itr = from;itr!= to){
            itr = erase(itr);
        }
        return to;
    }



};
template <typename Object>
class List<Object>::const_iterator{
    protected:
    Node *current;
    Object & retrieve() const{
        return current->data;
    }
    const_iterator(Node *p) : current{p}
    {}
    friend class List<Object>;
    public:
    const_iterator() : current{nullptr}
    {}
    const Object & operator* () const{
        return retrieve();
    }
    const_iterator & operator++(){
        current = current->next;
        return *this;
    }
    const_iterator & operator++(int){
        const_iterator old = *this;
        ++(*this);
        return old;
    }
    bool operator==(const const_iterator & rhs) const
    {
        return current == rhs.current;
    }
    bool operator!=(const const_iterator & rhs) const{
        return !(*this == rhs);
    }
    void assertIsValid() const{
        if(theList == nullprt || current == nullptr || current == theList->head)
            throw IteratorOutOfBoundsException{};
    }

    
};
template<typename Object>
class List<Object>::iterator : public const_iterator{
    public:
    iterator(){}
    Object & operator*(){
        return const_iterator::retrieve();
    }

    const Object & operator*() const{
        return const_iterator::operator*();

    }
    iterator & operator++(){
        this->current = this->current->next;
        return *this;
    }

    iterator operator++(int){
        iterator old = *this;
        ++(*this);
        return old;
    };
    protected:
    iterator(Node *p) : const_iterator{p}
    {}
    friend class List<Object>;

};

#endif